package leetcode.剑指offer.前40;

import leetcode.剑指offer.pojo.Node;
import org.junit.Test;

import java.util.HashMap;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/30 14:47
 * @description :
 */
public class 剑指_36_二叉搜索树与双向链表 {
    @Test
    public void test() {
        Solution solution = new Solution();
        Node root = new Node(4, new Node(2, new Node(1), new Node(3)), new Node(5));
        //Node root = new Node(2, null, null);
        //[-1,null,1,null,9]
        // Node root = new Node(-1, null, new Node(1, null, new Node(9)));
        Node head = solution.treeToDoublyList(root);
        while (head != null) {
            System.out.println(head.val);
            head = head.right;
        }
    }

    class Solution {

        Node head, pre;

        public Node treeToDoublyList(Node root) {
            if (root == null) return null;
            dfs(root);
            head.left = pre;
            pre.right = head;
            return head;
        }

        private void dfs(Node node) {
            if (node == null) return;
            dfs(node.left);
            if (pre != null) {
                pre.right = node;
            } else {
                head = node;
            }
            node.left = pre;
            pre = node;
            dfs(node.right);
        }
    }

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    '}';
        }
    }

    /*class Solution {
        Node head, pre;
        public Node treeToDoublyList(Node root) {
            if (root == null) return null;
            dfs(root);
            head.left = pre;
            pre.right = head;
            return head;
        }

        private void dfs(Node node) {
            if (node == null) return;
            dfs(node.left);
            if (pre != null) {
                pre.right = node;
            } else {
                head = node;
            }
            node.left = pre;
            pre = node;
            dfs(node.right);

        }
    }*/
}
